package q198_rob;

public class Solution_1 {
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.rob(new int[]{2, 7, 9, 3, 1}));
    }

    /**
     * 动态规划的另一道标准题
     * 我们考虑的是到n家时，f(n) 与 f(n - 1)的关系
     * 那么实际上有两个可能 f(n - 1)偷了第 n - 1 家，那么f(n)就不能偷n - 1家了
     * 还有一个可能就是f(n - 1)没偷
     * 所以偷没偷对于总值的影响在于，如果没偷的话 f(n) = f(n - 2) + nums[n]
     * 偷了则是f(n - 1) 比较大小才能决定是否选择偷n - 1
     * 所以就有了下面的方程
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length <= 2) {
            return nums.length == 1 ? nums[0] : Math.max(nums[1],nums[0]);
        }

        int[] robs = new int[nums.length];
        robs[0] = nums[0];
        robs[1] = Math.max(nums[1], nums[0]);
        for (int i = 2; i < nums.length; i++) {
            robs[i] = Math.max(robs[i - 2] + nums[i], robs[i - 1]);
        }

        return robs[nums.length - 1];
    }
}
